Improving clustering stability with combinatorial MRFs.

Data weaving scaling up the state%2Dof%2Dthe%2Dart in data clustering.

One%2DClass Clustering in the Text Domain.

Multi%2Dmodal Clustering for Multimedia Collections.


Web Page Clustering Using Heuristic Search in the Web Graph.


Combinatorial Markov Random Fields.
Abstract. A combinatorial random variable is a discrete random variable defined over a combinatorial set (e.g., a power set of a given set). In this paper we introduce combinatorial Markov random fields (Comrafs), which are Markov random fields where some of the nodes are combinatorial random variables. We argue that Comrafs are powerful models for unsupervised and semi-supervised learning. We put Comrafs in perspective by showing their relationship with several existing models. Since it can be problematic to apply existing inference techniques for graphical models to Comrafs, we design two simple and efficient inference algorithms specific for Comrafs, which are based on combinatorial optimization. We show that even such simple algorithms consistently and significantly outperform Latent Dirichlet Allocation (LDA) on a document clustering task. We then present Comraf models for semi-supervised clustering and transfer learning that demonstrate superior results in comparison to an existing semi-supervised scheme (constrained optimization). 1
Multi%2Dway distributional clustering via pairwise interactions.
We present a novel unsupervised learning scheme that simultaneously clusters variables of several types (e.g., documents, words and authors) based on pairwise interactions between the types, as observed in co-occurrence data. In this scheme, multiple clustering systems are generated aiming at maximizing an objective function that measures multiple pairwise mutual information between cluster variables. To implement this idea, we propose an algorithm that interleaves top-down clustering of some variables and bottom-up clustering of the other variables, with a local optimization correction routine. Focusing on document clustering we present an extensive empirical study of two-way, three-way and four-way applications of our scheme using six real-world datasets including the 20 Newsgroups (20NG) and the Enron email collection. Our multi-way distributional clustering (MDC) algorithms consistently and significantly outperform previous state-of-the-art information theoretic clustering algorithms. 1.
Disambiguating Web appearances of people in a social network.
Say you are looking for information about a particular person. A search engine returns many pages for that person’s name but which pages are about the person you care about, and which are about other people who happen to have the same name? Furthermore, if we are looking for multiple people who are related in some way, how can we best leverage this social network? This paper presents two unsupervised frameworks for solving this problem: one based on link structure of the Web pages, another using Agglomerative/Conglomerative Double Clustering (A/CDC)—an application of a recently introduced multi-way distributional clustering method. To evaluate our methods, we collected and hand-labeled a dataset of over 1000 Web pages retrieved from Google queries on 12 personal names appearing together in someones in an email folder. On this dataset our methods outperform traditional agglomerative clustering by more than 20%, achieving over 80 % F-measure.
Extracting social networks and contact information from email and the Web.
Abstract. We present an end-to-end system that extracts a user’s social network and its members’ contact information given the user’s email inbox. The system identifies unique people in email, finds their Web presence, and automatically fills the fields of a contact address book using conditional random fields—a type of probabilistic model well-suited for such information extraction tasks. By recursively calling itself on new people discovered on the Web, the system builds a social network with multiple degrees of separation from the user. Additionally, a set of expertise-describing keywords are extracted and associated with each person. We outline the collection of statistical and learning components that enable this system, and present experimental results on the real email of two users; we also present results with a simple method of learning transfer, and discuss the capabilities of the system for addressbook population, expert-finding, and social network analysis. 1
Distributional Word Clusters vs. Words for Text Categorization.
We study an approach to text categorization that combines distributional clustering of words and a  Support Vector Machine (SVM) classifier. This word-cluster representation is computed using the  recently introduced Information Bottleneck method, which generates a compact and efficient representation  of documents. When combined with the classification power of the SVM, this method  yields high performance in text categorization. This novel combination of SVM with word-cluster  representation is compared with SVM-based categorization using the simpler bag-of-words (BOW)  representation. The comparison is performed over three known datasets. On one of these datasets  (the 20 Newsgroups) the method based on word clusters significantly outperforms the word-based  representation in terms of categorization accuracy or representation efficiency. On the two other sets  (Reuters-21578 and WebKB) the word-based representation slightly outperforms the word-cluster  representation. We investigate the potential reasons for this behavior and relate it to structural  differences between the datasets.
On Feature Distributional Clustering for Text Categorization.
We describe a new powerful text categorization method that is based on a combination of distributional features with a support vector machine (SVM) classifier. Our feature selection approach uses distributional clustering of words via the recently introduced information bottleneck method, which generates a more e#cient representation of the documents. When combined with the classification power of Support Vector Machines we produce the best known multilabel categorization results on the 20 Newsgroups dataset.
